{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Make a Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到子序列的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>target</code> ，包含若干 <strong>互不相同</strong> 的整数，以及另一个整数数组 <code>arr</code> ，<code>arr</code> <strong>可能</strong> 包含重复元素。</p>\n",
    "\n",
    "<p>每一次操作中，你可以在 <code>arr</code> 的任意位置插入任一整数。比方说，如果 <code>arr = [1,4,1,2]</code> ，那么你可以在中间添加 <code>3</code> 得到 <code>[1,4,<strong>3</strong>,1,2]</code> 。你可以在数组最开始或最后面添加整数。</p>\n",
    "\n",
    "<p>请你返回 <strong>最少</strong> 操作次数，使得<em> </em><code>target</code><em> </em>成为 <code>arr</code> 的一个子序列。</p>\n",
    "\n",
    "<p>一个数组的 <strong>子序列</strong> 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，<code>[2,7,4]</code> 是 <code>[4,<strong>2</strong>,3,<strong>7</strong>,2,1,<strong>4</strong>]</code> 的子序列（加粗元素），但 <code>[2,4,2]</code> 不是子序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>target = [5,1,3], <code>arr</code> = [9,4,2,3,4]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>你可以添加 5 和 1 ，使得 arr 变为 [<strong>5</strong>,9,4,<strong>1</strong>,2,3,4] ，target 为 arr 的子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>target = [6,4,8,1,3,2], <code>arr</code> = [4,7,6,2,3,8,6,1]\n",
    "<b>输出：</b>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target.length, arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= target[i], arr[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>target</code> 不包含任何重复元素。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-make-a-subsequence](https://leetcode.cn/problems/minimum-operations-to-make-a-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-make-a-subsequence](https://leetcode.cn/problems/minimum-operations-to-make-a-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,1,3]\\n[9,4,2,3,4]', '[6,4,8,1,3,2]\\n[4,7,6,2,3,8,6,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        cache = {}\n",
    "        for i, v in enumerate(target):\n",
    "            cache[v] = i \n",
    "        \n",
    "        heaps = []\n",
    "        for i, v in enumerate(arr):\n",
    "            if v in cache:\n",
    "                v = cache[v]\n",
    "                l, r = 0, len(heaps)\n",
    "                while l < r:\n",
    "                    mid = (l+r)//2\n",
    "                    if heaps[mid] >= v:\n",
    "                        r = mid \n",
    "                    else:\n",
    "                        l = mid+1\n",
    "                    \n",
    "                if l < len(heaps) and heaps[l] >= v:\n",
    "                    heaps[l] = v \n",
    "                else:\n",
    "                    heaps.append(v)\n",
    "        return len(target)-len(heaps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        pos = {}\n",
    "        for i, t in enumerate(target):\n",
    "            pos[t] = i\n",
    "        d = []\n",
    "        for val in arr:\n",
    "            if val in pos:\n",
    "                idx = pos[val]\n",
    "                if not d:\n",
    "                    d.append(idx)\n",
    "                else:\n",
    "                    l, r = -1, len(d)\n",
    "                    while l + 1 < r:\n",
    "                        mi = (l + r) // 2\n",
    "                        if d[mi] < idx:\n",
    "                            l = mi\n",
    "                        else:\n",
    "                            r = mi\n",
    "                    if r == len(d):\n",
    "                        d.append(idx)\n",
    "                    else:\n",
    "                        d[r] = idx\n",
    "        return n - len(d)\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0\n",
    "        #     if target[i] == arr[j]:\n",
    "        #         return dfs(i - 1, j - 1) + 1\n",
    "        #     return max(dfs(i - 1, j), dfs(i, j - 1))\n",
    "\n",
    "        # return len(target) - dfs(len(target) - 1, len(arr) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "\n",
    "        idx_dict = {num: i for i, num in enumerate(target)}\n",
    "        stack = []\n",
    "        for num in arr:\n",
    "            if num in idx_dict:\n",
    "                idx = idx_dict[num]\n",
    "                i = bisect.bisect_left(stack, idx)\n",
    "\n",
    "                if i == len(stack):\n",
    "                    stack.append(0)\n",
    "                stack[i] = idx\n",
    "        return len(target) - len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        m, n = len(target), len(arr)\n",
    "        pos = dict()\n",
    "        for i in range(m):\n",
    "            pos[target[i]] = i\n",
    "        #print(pos)\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            if not s and arr[i] in pos:\n",
    "                s.append(pos[arr[i]])\n",
    "            if arr[i] in pos:\n",
    "                #print(arr[i], s[-1])\n",
    "                if pos[arr[i]] > pos[target[s[-1]]]:\n",
    "                    s.append(pos[arr[i]])\n",
    "                else:\n",
    "                    t = bisect_left(s, pos[arr[i]])\n",
    "                    s[t] = pos[arr[i]]\n",
    "        return m - len(s)\n",
    "                   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = []\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            l = 0\n",
    "            r = len(f) - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            if l >= len(f):\n",
    "                f.append(i)\n",
    "            else:\n",
    "                f[l] = i\n",
    "        return n - len(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 把target等价转换为 01234... 后求最长递增子序列\n",
    "        table = {}\n",
    "        for i in range(len(target)):\n",
    "            table[target[i]] = i\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in table:\n",
    "                arr[i] = table[arr[i]]\n",
    "            else:\n",
    "                arr[i] = -1\n",
    "        nums = []\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == -1:\n",
    "                continue\n",
    "            index = bisect.bisect_left(nums,arr[i])\n",
    "            if index == len(nums):\n",
    "                nums.append(arr[i])\n",
    "            else:\n",
    "                nums[index] = arr[i]\n",
    "        return len(target) - len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i,x in enumerate(target):\n",
    "            d[x]=i\n",
    "        \n",
    "        st = []\n",
    "        for x in arr:\n",
    "            if x not in d:\n",
    "                continue\n",
    "            ind = d[x]\n",
    "            if len(st)==0 or ind>st[-1]:\n",
    "                st.append(ind)\n",
    "            else:\n",
    "                pos = bisect.bisect_left(st, ind)\n",
    "                st[pos] = ind\n",
    "        \n",
    "        return len(target)-len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # def LCS(text1, text2):\n",
    "        #     R, C = len(text1) + 1, len(text2) + 1\n",
    "        #     dp = [[0] * C for i in range(R)]\n",
    "        #     for i in range(1, R):\n",
    "        #         for j in range(1, C):\n",
    "        #             if text1[i - 1] == text2[j - 1]:\n",
    "        #                 dp[i][j] = 1 + dp[i - 1][j - 1]\n",
    "        #             else:\n",
    "        #                 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])\n",
    "        #     return dp[-1][-1]\n",
    "        # return len(target) - LCS(target, arr)\n",
    "\n",
    "        d = {n: i for i, n in enumerate(target)}\n",
    "        def LIS(arr): # strictly increasing\n",
    "            LIS = []\n",
    "            for n in arr:\n",
    "                if n in d:\n",
    "                    i = bisect_left(LIS, d[n])\n",
    "                    if i == len(LIS):\n",
    "                        LIS.append(d[n])\n",
    "                    else:\n",
    "                        LIS[i] = d[n]\n",
    "            return len(LIS)   \n",
    "        return len(target) - LIS(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [-1]\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if f[-1] < i:\n",
    "                f.append(i)\n",
    "                continue\n",
    "            l = 0\n",
    "            r = len(f) - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - len(f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = []\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if not f or f[-1] < i:\n",
    "                f.append(i)\n",
    "                continue\n",
    "            l = 0\n",
    "            r = len(f) - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - len(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = {num: i for i, num in enumerate(target)}\n",
    "        dp = []\n",
    "        for x in arr:\n",
    "            if x in d:\n",
    "                i = bisect.bisect_left(dp, d[x])\n",
    "                if i == len(dp):\n",
    "                    dp.append(d[x])\n",
    "                else:\n",
    "                    dp[i] = d[x]\n",
    "\n",
    "        return len(target) - len(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        pos = {}\n",
    "        for i, t in enumerate(target):\n",
    "            pos[t] = i\n",
    "        d = []\n",
    "        for val in arr:\n",
    "            if val in pos:\n",
    "                idx = pos[val]\n",
    "                r = bisect.bisect_left(d, idx)\n",
    "                # l, r = -1, len(d)\n",
    "                # while l + 1 < r:\n",
    "                #     mi = (l + r) // 2\n",
    "                #     if d[mi] < idx:\n",
    "                #         l = mi\n",
    "                #     else:\n",
    "                #         r = mi\n",
    "                if r == len(d):\n",
    "                    d.append(idx)\n",
    "                else:\n",
    "                    d[r] = idx\n",
    "        return n - len(d)\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0\n",
    "        #     if target[i] == arr[j]:\n",
    "        #         return dfs(i - 1, j - 1) + 1\n",
    "        #     return max(dfs(i - 1, j), dfs(i, j - 1))\n",
    "\n",
    "        # return len(target) - dfs(len(target) - 1, len(arr) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [-1]\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if f[-1] < i:\n",
    "                f.append(i)\n",
    "            else:\n",
    "                l = 0\n",
    "                r = len(f) - 1\n",
    "                while l <= r:\n",
    "                    m = l + r >> 1\n",
    "                    if f[m] >= i:\n",
    "                        r = m - 1\n",
    "                    else:\n",
    "                        l = m + 1\n",
    "                f[l] = i\n",
    "        return n - len(f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # target = [5,1,3], arr = [5,9,4,2,3,4] [0, 2]\n",
    "        # d = {5: 0, 1: 1, 3: 2}\n",
    "        d = {n: i for i, n in enumerate(target)}\n",
    "        def LIS(arr): # strictly increasing\n",
    "            LIS = []\n",
    "            for n in arr:\n",
    "                if n in d:\n",
    "                    i = bisect_left(LIS, d[n])\n",
    "                    if i == len(LIS):\n",
    "                        LIS.append(d[n])\n",
    "                    else:\n",
    "                        LIS[i] = d[n]\n",
    "            return len(LIS)   \n",
    "        return len(target) - LIS(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        hash = {val: idx for idx, val in enumerate(target)}\n",
    "        # 问题转化为求最大递增子序列\n",
    "        # dp[i]表示长度为i的递增序列的最后一位\n",
    "        dp = [-float('inf')]\n",
    "        for c in arr:\n",
    "            if c not in hash:\n",
    "                continue\n",
    "            p = hash[c]\n",
    "            # print(p, end=': ')\n",
    "            if p > dp[-1]:\n",
    "                dp.append(p)\n",
    "                continue\n",
    "            if p <= dp[1]:\n",
    "                dp[1] = p\n",
    "                continue\n",
    "            # 二分查找，找到比p大的最左数字\n",
    "            left, right = 1, len(dp) - 1\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if dp[mid] < p:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            dp[left] = p\n",
    "            # print(dp)\n",
    "        # print()\n",
    "        # print(dp)\n",
    "        return len(target) - (len(dp) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        pos = {num: i for i, num in enumerate(target)}\n",
    "        seq = []\n",
    "        for num in arr:\n",
    "            if num in pos:\n",
    "                i = pos[num]\n",
    "                idx = bisect.bisect_left(seq, i)\n",
    "                if idx == len(seq):\n",
    "                    seq.append(i)\n",
    "                else:\n",
    "                    seq[idx] = i\n",
    "        return len(target) - len(seq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [-1]\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if f[-1] < i:\n",
    "                f.append(i)\n",
    "            else:\n",
    "                f[bisect_left(f, i)] = i\n",
    "        return n - len(f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [-1]\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if f[-1] < i:\n",
    "                f.append(i)\n",
    "            else:\n",
    "                f[bisect_left(f, i)] = i\n",
    "        return n - len(f) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\r\n",
    "class Solution:\r\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\r\n",
    "        # target is mapped to [0, 1, ...], finding lcs of target and arr\r\n",
    "        # is equivalent to finding lis of mapped arr\r\n",
    "        indices = {tgt: i for i, tgt in enumerate(target)}\r\n",
    "        lis: list[int] = list()\r\n",
    "        for num in arr:\r\n",
    "            if num not in indices: continue\r\n",
    "            x = bisect_left(lis, indices[num])\r\n",
    "            if x == len(lis):\r\n",
    "                lis.append(indices[num])\r\n",
    "            else:\r\n",
    "                lis[x] = indices[num]\r\n",
    "        \r\n",
    "        return len(target) - len(lis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\r\n",
    "class Solution:\r\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\r\n",
    "        # target is mapped to [0, 1, ...], finding lcs of target and arr\r\n",
    "        # is equivalent to finding lis of mapped arr\r\n",
    "        indices = {tgt: i for i, tgt in enumerate(target)}\r\n",
    "        lis: list[int] = list()\r\n",
    "        for num in arr:\r\n",
    "            if num not in indices: continue\r\n",
    "            x = bisect_left(lis, indices[num])\r\n",
    "            if x == len(lis):\r\n",
    "                lis.append(indices[num])\r\n",
    "            else:\r\n",
    "                lis[x] = indices[num]\r\n",
    "        \r\n",
    "        return len(target) - len(lis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        f[0] = -1\n",
    "        idx = 1\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            if i > f[idx - 1]:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "                continue\n",
    "            l = 1\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - idx + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        m = len(target)\n",
    "        mapper = {}\n",
    "        for i in range(m):\n",
    "            mapper[target[i]] = i\n",
    "        \n",
    "        brr = []\n",
    "        for a in arr:\n",
    "            if a in mapper.keys():\n",
    "                brr.append(mapper[a])\n",
    "        \n",
    "        n = len(brr)\n",
    "        if n == 0:\n",
    "            return m\n",
    "\n",
    "        stack = [brr[0]]\n",
    "        for i in range(1, n):\n",
    "            if brr[i] > stack[-1]:\n",
    "                stack.append(brr[i])\n",
    "            else:\n",
    "                l, r = 0, len(stack) - 1\n",
    "                while l < r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if stack[mid] < brr[i]:\n",
    "                        l = mid + 1\n",
    "                    else:\n",
    "                        r = mid\n",
    "                stack[l] = brr[i]\n",
    "        return m - len(stack)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        idx = 0\n",
    "        for x in arr:\n",
    "            i = d.get(x, -1)\n",
    "            if i == -1:\n",
    "                continue\n",
    "            l = 0\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            if l >= idx:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "            else:\n",
    "                f[l] = i\n",
    "        return n - idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict(zip(target, range(len(target))))\n",
    "        arr = list(map(lambda x: d[x], filter(lambda x: x in d, arr)))\n",
    "\n",
    "        dp = [-inf]\n",
    "        for a in arr:\n",
    "            if a > dp[-1]: dp.append(a)\n",
    "            else: dp[bisect_left(dp, a)] = a\n",
    "        return len(target) - (len(dp) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        hst = {num: i for i, num in enumerate(target)}\n",
    "        nums = []\n",
    "        for a in arr:\n",
    "            if a in hst:\n",
    "                nums.append(hst[a])\n",
    "        \n",
    "        d = []\n",
    "        for n in nums:\n",
    "            if not d or n > d[-1]:\n",
    "                d.append(n)\n",
    "            else:\n",
    "                loc =  bisect.bisect_left(d, n)\n",
    "                d[loc] = n\n",
    "        return len(target) - len(d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = {num:i + 1 for i, num in enumerate(target)}\n",
    "        nums = [d[i] for i in arr if i in d]\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return len(d)\n",
    "        dp = []\n",
    "        for i in range(n):\n",
    "            pos = bisect.bisect_left(dp, nums[i])\n",
    "            if pos >= len(dp):\n",
    "                dp.append(nums[i])\n",
    "            else:\n",
    "                dp[pos] = nums[i]\n",
    "        return len(d) - len(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 找target 和 arr 的最长公共子序列\n",
    "\n",
    "        # 根据target中互不相同，我们知道每个数字对应的坐标唯一\n",
    "\n",
    "        # 于是最长公共子序列等价于arr用target的坐标转换后构成对应的下标数组的“最长递增子序列”\n",
    "\n",
    "\n",
    "        # 数字对应坐标\n",
    "        idx_dict = {num: i for i, num in enumerate(target)}\n",
    "        # 300.最长上升子序列\n",
    "        dp = [0] * len(arr)\n",
    "        res = 0\n",
    "        for num in arr:\n",
    "            # 只有在target的数字才可能属于公共子序列\n",
    "            if num in idx_dict:\n",
    "                # 转换坐标\n",
    "                idx = idx_dict[num]\n",
    "                # 该坐标在当前栈中的位置\n",
    "                left, right = 0, res\n",
    "                while left + 1 < right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if dp[mid] < idx:\n",
    "                        left = mid \n",
    "                    else:\n",
    "                        right = mid\n",
    "                if dp[left] >= idx:\n",
    "                    dp[left] = idx\n",
    "                    if left == res: res += 1\n",
    "                else:\n",
    "                    dp[right] = idx\n",
    "                    if right == res: res += 1\n",
    "                # 如果在最后要加入元素，否则要修改该位置的元素\n",
    "                # 跟一般的讲，i代表了目前这个idx在stack中的大小位置，\n",
    "                # 在前面出现还比idx大的stack中的元素是无法和idx构成最长上升子序列的。\n",
    "                # i左边的数比idx小，可以和idx构成上升子序列，(idx构成的长度就是i+1)\n",
    "                # idx比i的值小，将i替换后可以方便后面构成更优的子序列(越小后面能加入的数越多)\n",
    "\n",
    "\n",
    "        # 最终stack的长度就构成了最长上升子序列的长度，用减法即可得到本题答案\n",
    "        return len(target) - res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        dt = dict()\n",
    "        for i, t in enumerate(target):\n",
    "            dt[t] = i\n",
    "\n",
    "        newarr = []\n",
    "\n",
    "        for a in arr:\n",
    "            if a in dt:\n",
    "                newarr.append(dt[a])\n",
    "        \n",
    "        n = len(newarr)\n",
    "\n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            if not tmp:\n",
    "                tmp.append(newarr[i])\n",
    "            else:\n",
    "                if newarr[i] > tmp[-1]:\n",
    "                    tmp.append(newarr[i])\n",
    "                else:\n",
    "                    pos = bisect.bisect_left(tmp, newarr[i] )\n",
    "                    tmp[pos] = newarr[i]\n",
    "        return len(target) - len(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        dictA = dict()\n",
    "        for i,t in enumerate(target):\n",
    "            dictA[t] = i   \n",
    "        arr_map = []\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in dictA:\n",
    "                arr_map.append(dictA[arr[i]])\n",
    "        \n",
    "        longest = self.lengthOfLIS(arr_map)\n",
    "        return len(target) - longest\n",
    "\n",
    "\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        res = [nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>res[-1]:\n",
    "                res.append(nums[i])\n",
    "            else:\n",
    "                idx = bisect_left(res, nums[i])\n",
    "                res[idx] = nums[i]\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 求最长公共子序列，用n-最长公共子序列的长度就是最少插入次数\n",
    "        # 因为target数组各不相同，所以每个元素与index一一对应，\n",
    "        pos={x:i for i,x in enumerate(target)}\n",
    "        index=[]\n",
    "        for x in arr:\n",
    "            if x in pos:index.append(pos[x])\n",
    "        dp=[]\n",
    "        for x in index:\n",
    "            if not dp or x>dp[-1]:\n",
    "                dp.append(x)\n",
    "            else:\n",
    "                index=bisect.bisect_left(dp,x)\n",
    "                dp[index]=x \n",
    "        return len(target)-len(dp)\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        my_dict = {}\n",
    "        for i, x in enumerate(target):\n",
    "            my_dict[x] = i\n",
    "        \n",
    "        # Only keep the elements in arr that also exist in target\n",
    "        new_arr = [my_dict[val] for val in arr if val in my_dict]\n",
    "\n",
    "        # Find the length of LIS in new_arr\n",
    "        lis = []\n",
    "        for x in new_arr:\n",
    "            idx = self.binary_search(lis, x)\n",
    "            if idx == len(lis):\n",
    "                lis.append(x)\n",
    "            else:\n",
    "                lis[idx] = x\n",
    "\n",
    "        return len(target) - len(lis)\n",
    "    \n",
    "    def binary_search(self, lis, x):\n",
    "        l, r = 0, len(lis) - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if lis[mid] < x:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        my_dict = {}\n",
    "        for i, x in enumerate(target):\n",
    "            my_dict[x] = i\n",
    "        \n",
    "        # Only keep the elements in arr that also exist in target\n",
    "        new_arr = [my_dict[val] for val in arr if val in my_dict]\n",
    "\n",
    "        # Find the length of LIS in new_arr\n",
    "        lis = []\n",
    "        for x in new_arr:\n",
    "            idx = self.binary_search(lis, x)\n",
    "            if idx == len(lis):\n",
    "                lis.append(x)\n",
    "            else:\n",
    "                lis[idx] = x\n",
    "\n",
    "        return len(target) - len(lis)\n",
    "    \n",
    "    def binary_search(self, lis, x):\n",
    "        l, r = 0, len(lis) \n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if lis[mid] < x:\n",
    "                l = mid +1\n",
    "            else:\n",
    "                r = mid \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        v_idx = {v: i for i, v in enumerate(target)}\n",
    "        nums = [v_idx[v] for v in arr if v in v_idx]\n",
    "        n = len(nums)\n",
    "        min_end = [-1]\n",
    "        for v in nums:\n",
    "            i = bisect.bisect_left(min_end, v)\n",
    "            if i < len(min_end):\n",
    "                min_end[i] = min(min_end[i], v)\n",
    "            else:\n",
    "                min_end.append(v)\n",
    "        return len(target) - len(min_end) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        dic = {}\n",
    "        for i in range(len(target)):\n",
    "            dic[target[i]] = i\n",
    "        array = []\n",
    "        for a in arr:\n",
    "            if a in dic:\n",
    "                array.append(dic[a])\n",
    "        new = []\n",
    "        for a in array:\n",
    "            if not new or new[-1] < a:\n",
    "                new.append(a)\n",
    "            else:\n",
    "                idx = bisect_left(new, a)\n",
    "                new[idx] = a\n",
    "        return len(target) - len(new)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class LongestIncreasingSubsequence:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def definitely_increase(nums):\n",
    "        # 最长单调递增子序列（严格上升）\n",
    "        dp = []\n",
    "        for num in nums:\n",
    "            i = bisect.bisect_left(dp, num)\n",
    "            if 0 <= i < len(dp):\n",
    "                dp[i] = num\n",
    "            else:\n",
    "                dp.append(num)\n",
    "        return len(dp)\n",
    "\n",
    "    @staticmethod\n",
    "    def definitely_not_reduce(nums):\n",
    "        # 最长单调不减子序列（不降）\n",
    "        dp = []\n",
    "        for num in nums:\n",
    "            i = bisect.bisect_right(dp, num)\n",
    "            if 0 <= i < len(dp):\n",
    "                dp[i] = num\n",
    "            else:\n",
    "                dp.append(num)\n",
    "        return len(dp)\n",
    "\n",
    "    def definitely_reduce(self, nums):\n",
    "        # 最长单调递减子序列（严格下降）\n",
    "        nums = [-num for num in nums]\n",
    "        return self.definitely_increase(nums)\n",
    "\n",
    "    def definitely_not_increase(self, nums):\n",
    "        # 最长单调不增子序列（不升）\n",
    "        nums = [-num for num in nums]\n",
    "        return self.definitely_not_reduce(nums)\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        ind = {num: i for i, num in enumerate(target)}\n",
    "        lst = [ind[num] for num in arr if num in ind]\n",
    "        return len(target) - LongestIncreasingSubsequence().definitely_increase(lst)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        n, m = len(target), len(arr)\n",
    "        mapping = {target[i]: i for i in range(n)}\n",
    "        indices = [mapping[arr[i]] for i in range(m) if arr[i] in mapping]\n",
    "        indices_length = len(indices)\n",
    "        max_len, g = 0, [float('inf')] * (indices_length + 1)\n",
    "\n",
    "        for i in range(indices_length):\n",
    "            t = indices[i]\n",
    "            l, r = 0, indices_length\n",
    "            while l < r:\n",
    "                mid = (l + r + 1) // 2\n",
    "                if g[mid] < t:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            clen = r + 1\n",
    "            max_len = max(max_len, clen)\n",
    "            g[clen] = min(g[clen], t)\n",
    "\n",
    "        return n - max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        m, n = len(target), len(arr)\n",
    "        p = {}\n",
    "        for i, num in enumerate(target):\n",
    "            p[num] = i\n",
    "\n",
    "        tmp = []\n",
    "        for num in arr:\n",
    "            if num in p:\n",
    "                tmp.append(p[num])\n",
    "        d = []\n",
    "        for num in tmp:\n",
    "            if not d or num > d[-1]:\n",
    "                d.append(num)\n",
    "            else:\n",
    "                idx = bisect.bisect_left(d, num)\n",
    "                d[idx] = num\n",
    "        # print(d)\n",
    "        return m - len(d)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 因为target元素互不相同，用哈希表构建target元素和下标之间的映射\n",
    "        # 将arr中的target元素映射为下标，因为要使得target是arr的一个子序列，\n",
    "        # 那么映射后下标肯定要从0到len(target)-1\n",
    "        # 所以算出已有的最长递增子序列，则已有的这些是不用添加了，只需要再添加缺少的就行\n",
    "        dictA = dict()\n",
    "        for i,t in enumerate(target):\n",
    "            dictA[t] = i   \n",
    "        arr_map = []\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in dictA:\n",
    "                arr_map.append(dictA[arr[i]])\n",
    "        \n",
    "        longest = self.lengthOfLIS(arr_map)\n",
    "        return len(target) - longest\n",
    "\n",
    "\n",
    "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        res = [nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>res[-1]:\n",
    "                res.append(nums[i])\n",
    "            else:\n",
    "                idx = bisect_left(res, nums[i])\n",
    "                res[idx] = nums[i]\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# LIS problem : Longest Increasing Subsequence\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        def LIS(nums):\n",
    "            # dp[i] : the smallest ending number of subsequence that has length i+1\n",
    "            dp = []\n",
    "            for x in nums:\n",
    "                idx = bisect_left(dp,x)\n",
    "                if idx == len(dp):\n",
    "                    dp.append(x)\n",
    "                else:\n",
    "                    dp[idx] = x\n",
    "            return len(dp)\n",
    "\n",
    "        M = {x:i for i,x in enumerate(target)}\n",
    "        C = [M[x] for x in arr if x in M]\n",
    "        return len(target) - LIS(C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        # 将target中的数字映射到其索引\n",
    "        index_map = {num: i for i, num in enumerate(target)}\n",
    "        \n",
    "        # 将arr转换为其在target中的索引表示\n",
    "        # 只保留target中存在的数字\n",
    "        stack = []\n",
    "        for num in arr:\n",
    "            if num in index_map:\n",
    "                stack.append(index_map[num])\n",
    "        \n",
    "        # 在stack中找最长递增子序列\n",
    "        lis = []\n",
    "        for num in stack:\n",
    "            idx = bisect.bisect_left(lis, num)\n",
    "            if idx == len(lis):\n",
    "                lis.append(num)\n",
    "            else:\n",
    "                lis[idx] = num\n",
    "        \n",
    "        # 返回需要插入的元素数量\n",
    "        return len(target) - len(lis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\r\n",
    "        target_index = dict()\r\n",
    "        for i in range(len(target)):\r\n",
    "            target_index[target[i]] = i\r\n",
    "        actual = []\r\n",
    "        for n in arr:\r\n",
    "            if n in target_index:\r\n",
    "                actual.append(target_index[n])\r\n",
    "        # 如果actual中可以被用来顶一顶组成target，要求index能组成LIS，剩余部分都得补\r\n",
    "        # n^2 LIS 超时\r\n",
    "        # def LIS(nums):\r\n",
    "        #     n = len(nums)\r\n",
    "        #     if n == 0:\r\n",
    "        #         return 0\r\n",
    "        #     dp = [1] * n\r\n",
    "        #     for i in range(n):\r\n",
    "        #         for j in range(i):\r\n",
    "        #             if nums[i] > nums[j]:\r\n",
    "        #                 dp[i] = max(dp[i], dp[j] + 1)\r\n",
    "        #     return max(dp)\r\n",
    "        def LIS(nums):\r\n",
    "            if len(nums) == 0:\r\n",
    "                return 0\r\n",
    "            d = []\r\n",
    "            for n in nums:\r\n",
    "                if not d or n > d[-1]:\r\n",
    "                    d.append(n)\r\n",
    "                else:\r\n",
    "                    l, r = 0, len(d) - 1\r\n",
    "                    loc = r\r\n",
    "                    while l <= r:\r\n",
    "                        mid = (l + r) // 2\r\n",
    "                        if d[mid] >= n:\r\n",
    "                            loc = mid\r\n",
    "                            r = mid - 1\r\n",
    "                        else:\r\n",
    "                            l = mid + 1\r\n",
    "                    d[loc] = n\r\n",
    "            return len(d)\r\n",
    "        return len(target) - LIS(actual)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        target = [5,1,3], arr = [9,4,2,3,4]\n",
    "        :param target:\n",
    "        :param arr:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = {}\n",
    "        for k,v in enumerate(target):\n",
    "            m1[v] = k\n",
    "        arr2 = []\n",
    "        for i in arr:\n",
    "            if i not in m1:\n",
    "                continue\n",
    "            arr2.append(m1.get(i, -1))\n",
    "        dp = []\n",
    "        for i in arr2:\n",
    "            if not dp or i > dp[-1]:\n",
    "                dp.append(i)\n",
    "            else:\n",
    "                tag = bisect_left(dp, i)\n",
    "                if tag == len(dp):\n",
    "                    tag -= 1\n",
    "                dp[tag] = i\n",
    "\n",
    "        return len(target) - len(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict(zip(target, range(len(target))))\n",
    "        arr = list(map(lambda x: d[x], filter(lambda x: x in d, arr)))\n",
    "\n",
    "        dp = [-inf]\n",
    "        for a in arr:\n",
    "            if a > dp[-1]: dp.append(a)\n",
    "            else: dp[bisect_left(dp, a)] = a\n",
    "        return len(target) - (len(dp) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        f[0] = -1\n",
    "        idx = 1\n",
    "        for x in arr:\n",
    "            if x not in d:\n",
    "                continue\n",
    "            i = d[x]\n",
    "            if i > f[idx - 1]:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "                continue\n",
    "            l = 1\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - idx + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "\t\ttarget_dict = {}\n",
    "\t\tfor index, data in enumerate(target):\n",
    "\t\t\ttarget_dict[data] = index\n",
    "\t\tarr_copy = copy.deepcopy(arr)\n",
    "\t\tfor index, data in enumerate(arr):\n",
    "\t\t\tposition = target_dict.get(data, -1)\n",
    "\t\t\tarr_copy[index] = position\n",
    "\t\tif max(arr_copy) == -1:\n",
    "\t\t\treturn len(target)\n",
    "\t\t# 遍历数组\n",
    "\t\ttest = self.lengthOfLIS_2(arr_copy)\n",
    "\t\treturn len(target) - test\n",
    "\t\n",
    "\tdef lengthOfLIS_2(self, nums):\n",
    "\t\tnums_copy = []\n",
    "\t\tfor data in nums:\n",
    "\t\t\tif data != -1:\n",
    "\t\t\t\tnums_copy.append(data)\n",
    "\t\ttailor = [0 for i in range(len(nums_copy))]\n",
    "\t\tlength = 1\n",
    "\t\ttailor[0] = nums_copy[0]\n",
    "\t\tfor num in nums_copy[1:]:\n",
    "\t\t\tindex = bisect.bisect_left(tailor[0: length], num)\n",
    "\t\t\ttailor[index] = num\n",
    "\t\t\tif index == length:\n",
    "\t\t\t\tlength += 1\n",
    "\t\treturn length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        f[0] = -1\n",
    "        idx = 1\n",
    "        for x in arr:\n",
    "            i = d.get(x)\n",
    "            if i is None:\n",
    "                continue\n",
    "            if i > f[idx - 1]:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "                continue\n",
    "            l = 1\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - idx + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        idx = 0\n",
    "        for x in arr:\n",
    "            i = d.get(x)\n",
    "            if i is None:\n",
    "                continue\n",
    "            if idx == 0 or i > f[idx - 1]:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "                continue\n",
    "            l = 0\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            f[l] = i\n",
    "        return n - idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        rs = []\n",
    "        maxlen = 0\n",
    "        target_dict = dict(zip(target, list(range(len(target)))))\n",
    "        arr_ind = []\n",
    "        rs = []\n",
    "        maxlen = 0\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in target_dict.keys():\n",
    "                continue\n",
    "            val = target_dict[arr[i]]\n",
    "            ind = bisect.bisect_left(rs,val)\n",
    "            if ind==len(rs):\n",
    "                rs.append(val)\n",
    "            else:\n",
    "                rs[ind]=val\n",
    "        return len(target)-len(rs)\n",
    "        # for i in range(len(arr)):\n",
    "        #     if arr[i] in target_dict.keys():\n",
    "        #         arr_ind.append(target_dict[arr[i]])\n",
    "        #         rs.append(1)\n",
    "        #     else:\n",
    "        #         arr_ind.append(-1)\n",
    "        #         rs.append(0)\n",
    "        #         continue\n",
    "        #     for j in range(i):\n",
    "        #         if arr_ind[j]>=0 and arr_ind[i]>arr_ind[j]:\n",
    "        #             rs[i] = max(rs[i],rs[j]+1)\n",
    "        #     maxlen = max(maxlen,rs[i])\n",
    "            \n",
    "        # target_dict = dict(zip(target,[[] for _ in range(len(target))]))\n",
    "        # for i in range(len(arr)):\n",
    "        #     if arr[i] in target_dict.keys():\n",
    "        #         target_dict[arr[i]].append(i)\n",
    "\n",
    "        # for i in range(len(target)):\n",
    "        #     indicies = target_dict[target[i]]\n",
    "        #     rs.append([])\n",
    "        #     for j in indicies:\n",
    "        #         if arr[j]==target[i]:\n",
    "        #             rs[i].append([1,j])\n",
    "        #             for k in range(i):\n",
    "        #                 for l in rs[k]:\n",
    "        #                     if l[1]<j and l[0]+1>rs[i][-1][0]:\n",
    "        #                         rs[i][-1][0] = l[0]+1\n",
    "        #             maxlen = max(maxlen,rs[i][-1][0])\n",
    "        return len(target)-maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "\t\ttarget_dict = {}\n",
    "\t\tfor index, data in enumerate(target):\n",
    "\t\t\ttarget_dict[data] = index\n",
    "\t\tarr_copy = copy.deepcopy(arr)\n",
    "\t\tfor index, data in enumerate(arr):\n",
    "\t\t\tposition = target_dict.get(data, -1)\n",
    "\t\t\tarr_copy[index] = position\n",
    "\t\tif max(arr_copy) == -1:\n",
    "\t\t\treturn len(target)\n",
    "\t\tdp = [1] * len(arr_copy)\n",
    "\t\t# 遍历数组\n",
    "\t\ttest = self.lengthOfLIS(arr_copy)\n",
    "\t\t# for i in range(len(arr_copy)):\n",
    "\t\t# \tfor j in range(i):\n",
    "\t\t# \t\tif arr_copy[i] > arr_copy[j] != -1:\n",
    "\t\t# \t\t\tdp[i] = max(dp[i], dp[j] + 1)\n",
    "\t\t# print(dp, )\n",
    "\t\treturn len(target) - test\n",
    "\t\n",
    "\tdef lengthOfLIS(self, nums):\n",
    "\t\tif not nums:\n",
    "\t\t\treturn 0\n",
    "\t\t\n",
    "\t\t# 创建一个辅助数组tails，用于存储递增子序列的尾部元素\n",
    "\t\ttails = [0] * len(nums)\n",
    "\t\t# 初始化最长递增子序列的长度为1\n",
    "\t\tlength = 0\n",
    "\t\t\n",
    "\t\t# 遍历输入数组\n",
    "\t\tfor num in nums:\n",
    "\t\t\tif num == -1:\n",
    "\t\t\t\tcontinue\n",
    "\t\t\t# 使用二分查找在tails数组中找到适合插入的位置\n",
    "\t\t\tleft, right = 0, length - 1\n",
    "\t\t\twhile left <= right:\n",
    "\t\t\t\tmid = (left + right) // 2\n",
    "\t\t\t\tif tails[mid] < num:\n",
    "\t\t\t\t\tleft = mid + 1\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tright = mid - 1\n",
    "\t\t\t\n",
    "\t\t\t# 将num插入到tails数组中，如果num比当前递增子序列的尾部元素都大，就追加到最后\n",
    "\t\t\ttails[left] = num\n",
    "\t\t\t# 如果插入位置是当前递增子序列的尾部，递增子序列长度加1\n",
    "\t\t\tif left == length:\n",
    "\t\t\t\tlength += 1\n",
    "\t\t\n",
    "\t\treturn length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        d = dict()\n",
    "        n = len(target)\n",
    "        for i in range(n):\n",
    "            d[target[i]] = i\n",
    "        f = [0] * n\n",
    "        idx = 0\n",
    "        for x in arr:\n",
    "            i = d.get(x)\n",
    "            if i is None:\n",
    "                continue\n",
    "            l = 0\n",
    "            r = idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if f[m] >= i:\n",
    "                    r = m - 1\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            if l >= idx:\n",
    "                f[idx] = i\n",
    "                idx += 1\n",
    "            else:\n",
    "                f[l] = i\n",
    "        return n - idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        D = {i:idx for idx,i in enumerate(target)}\n",
    "        L = []\n",
    "        for i in arr:\n",
    "            if i in D:L.append(D[i])\n",
    "        if not L:return len(target)\n",
    "        Res = [L[0]]\n",
    "        for i in L[1:]:\n",
    "            if i > Res[-1]:Res.append(i)\n",
    "            else:\n",
    "                Res[bisect_left(Res,i)] = i\n",
    "        return len(target)-len(Res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, t: List[int], a: List[int]) -> int:\n",
    "        s = {t[j]:j for j in range(len(t))}\n",
    "        a = [s[j] for j in a if j in s]\n",
    "    \n",
    "        b = []\n",
    "        for j in a[:]:\n",
    "            i = bisect_left(b, j)\n",
    "            if i==len(b):\n",
    "                b.append(j)\n",
    "            else:\n",
    "                b[i] = j \n",
    "        return len(t) - len(b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,n):\n",
    "        self.F = [0] * 4*n\n",
    "    \n",
    "    def update(self,o,l,r,a,b,mx):\n",
    "        if l == r:self.F[o] = mx;return\n",
    "        if a <= l and r <= b:\n",
    "            self.F[o] = max(self.F[o],mx)\n",
    "            return\n",
    "        m = (l+r)>>1\n",
    "        if a <= m:\n",
    "            self.update(2*o,l,m,a,b,mx)\n",
    "        if m+1 <= b:\n",
    "            self.update(2*o+1,m+1,r,a,b,mx)\n",
    "        self.F[o] = max(self.F[2*o],self.F[2*o+1])\n",
    "        return\n",
    "\n",
    "    def query(self,o,l,r,a,b):\n",
    "        if l == r or a <= l and r <= b:return self.F[o]\n",
    "        res = 0\n",
    "        m = (l+r)>>1\n",
    "        if m >= a:res = max(res,self.query(2*o,l,m,a,b))\n",
    "        if m+1 <= b:res = max(self.query(2*o+1,m+1,r,a,b),res)\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        D = {i:idx for idx,i in enumerate(target)}\n",
    "        n = len(target)\n",
    "        Tr = SegTree(n)\n",
    "        for idx,i in enumerate(arr):\n",
    "            if i not in D:continue\n",
    "            if D[i] == 0:mx = 1\n",
    "            else:mx = Tr.query(1,0,n-1,0,D[i]-1)+1\n",
    "            Tr.update(1,0,n-1,D[i],D[i],mx)\n",
    "        return n - Tr.F[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        my_dict = {}\n",
    "        for i, x in enumerate(target):\n",
    "            my_dict[x] = i\n",
    "        \n",
    "        def binary_search(lis, x):\n",
    "            left, right = 0, len(lis)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if lis[mid] < x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        \n",
    "        lis = []\n",
    "        my_set=set(target)\n",
    "        for x in arr:\n",
    "            if x not in my_set:\n",
    "                continue\n",
    "            x = my_dict[x]\n",
    "            my_loc = binary_search(lis, x)\n",
    "            if my_loc == len(lis):\n",
    "                lis.append(x)\n",
    "            else:\n",
    "                lis[my_loc] = x\n",
    "\n",
    "        return len(target) - len(lis)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self,n,L):\n",
    "        self.F = [0] * (4*n)\n",
    "        self.lz = [0] * (4*n)\n",
    "        self.n = n\n",
    "        self.L = L\n",
    "\n",
    "    def maintain(self,o):\n",
    "        self.F[o] = max(self.F[2*o],self.F[2*o+1])\n",
    "        return\n",
    "\n",
    "    def build(self,o,l,r):\n",
    "        if l == r-1:\n",
    "            self.F[o] = self.L[l]\n",
    "            return\n",
    "        m = (l+r)//2\n",
    "        self.build(2*o,l,m)\n",
    "        self.build(2*o+1,m,r)\n",
    "        self.maintain(o)        \n",
    "        return\n",
    "        \n",
    "\n",
    "    def update(self,o,l,r,a,b,v):\n",
    "        if l == r-1:self.F[o] = max(self.F[o],v);return\n",
    "        elif a <= l and r <= b:\n",
    "            if v > self.F[o]:\n",
    "                self.F[o] = v\n",
    "                self.lz[o] = v\n",
    "            return\n",
    "        m = (l+r)//2\n",
    "        if self.lz[o]:\n",
    "            if v > self.F[2*o]:\n",
    "                self.F[2*o] = v\n",
    "                self.lz[2*o] = v\n",
    "            if v > self.F[2*o+1]:\n",
    "                self.F[2*o+1] = v\n",
    "                self.lz[2*o+1] = v\n",
    "            self.lz[o] = 0\n",
    "        if m > a: \n",
    "            self.update(2*o,l,m,a,b,v)\n",
    "        if m < b:\n",
    "            self.update(2*o+1,m,r,a,b,v)\n",
    "        self.maintain(o)\n",
    "        return\n",
    "    \n",
    "    def query(self,o,l,r,a,b):\n",
    "        res = 0\n",
    "        if l == r or (a <= l and r <= b):return self.F[o]\n",
    "        m = (l+r)//2   \n",
    "        if m > a:\n",
    "            res = max(res,self.query(2*o,l,m,a,b))\n",
    "        if m < b:\n",
    "            res = max(res,self.query(2*o+1,m,r,a,b))\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        D = {i:idx for idx,i in enumerate(target)}\n",
    "        n = len(target)\n",
    "        Tr = SegTree(n,[0]*n)\n",
    "        for idx,i in enumerate(arr):\n",
    "            if i not in D:continue\n",
    "            if D[i] == 0:mx = 1\n",
    "            else:mx = Tr.query(1,0,n,0,D[i])+1\n",
    "            Tr.update(1,0,n,D[i],D[i]+1,mx)\n",
    "        return n - Tr.F[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2023-09-22 15:52:53\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        s = set(target)\n",
    "\n",
    "        mp = {v: i for i, v in enumerate(target)}\n",
    "        a = []\n",
    "\n",
    "        for x in arr:\n",
    "            if x in s:\n",
    "                a.append(mp[x])\n",
    "\n",
    "        # print(a)\n",
    "        n = len(target)\n",
    "\n",
    "        def lcs(a):\n",
    "            q = []\n",
    "            for x in a:\n",
    "                if not q or x > q[-1]:\n",
    "                    q.append(x)\n",
    "                else:\n",
    "                    i = bisect_left(q, x)\n",
    "                    q[i] = x\n",
    "            return len(q)\n",
    "\n",
    "        return n - lcs(a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, target: List[int], arr: List[int]) -> int:\n",
    "        t=dict([(n,i) for i,n in enumerate(target)])\n",
    "        aa=[t[x] for x in arr if x in t]\n",
    "        a=[100001]*len(aa)\n",
    "        for n in aa:a[bisect.bisect_left(a,n)]=n\n",
    "        return len(target)-len([x for x in a if x!=100001])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
